﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Chapter_9__Recursion_
{
    public static class Ex_9_2
    {
        static bool UseDynamicProgramming = true;

        public static long HowManyPaths(int destX, int destY)
        {
            long[,] values = new long[destX + 1, destY + 1];

            DateTime start = DateTime.Now;
            long result = HowManyPaths(destX, destY, 0, 0, values);
            TimeSpan elapsedTime = DateTime.Now - start;
            double milliseconds = elapsedTime.TotalMilliseconds;

            return result;
        }

        static long HowManyPaths(int destX, int destY, int currentX, int currentY, long[,] Values)
        {
            if (currentX > destX || currentY > destY)
                return 0;
            else if (currentX == destX && currentY == destY)
                return 1;
            else if (UseDynamicProgramming && Values[currentX, currentY] > 0)
                return Values[currentX, currentY];

            long Paths =
                HowManyPaths(destX, destY, currentX + 1, currentY, Values) +
                HowManyPaths(destX, destY, currentX, currentY + 1, Values);

            Values[currentX, currentY] = Paths;
            return Paths;
        }
    }
}
